#include <math.h>
#include <stdlib.h>
#include <unistd.h>

#include <iostream>
#include <vector>

#include "gsolverBBPv3.h"

using namespace std ;

/**
 * A BBP solver : starts with jobs with last due dates
 *
 * Dans cette version 3 de la BBP, on demarre avec les jobs reordonnes dans le sens des dates dues croissantes. Mais
 * contrairement a l'exploration brutale de la version 2, cette fois on ne considere pas n'importe quel numero de batch.
 * Pour chaque job, on choisit de le rajouter soit dans un batch deja existant dont la capacite residuel est suffisante
 * pour stocker le nouveau job, soit dans un nouveau batch.
 *
 * Le nouveau batch est ordonnance avant les autres batchs deja crees.
 *
 * ATTENTION : Pour que cette solution soit optimale, sachant que l'on
 * part d'un probleme pour lequel les jobs sont classes par date due croissante, il est egalement necessaire que le cout de stockage
 * de tous les jobs soient identiques. Dans le cas contraire, la solution ainsi construite n'est plus certaine d'etre optimale.
 */
GSolverBBPv3::GSolverBBPv3(GSupplyLinkProblem& pb, int node_, int p_):problem(pb),bestSolution(pb),bestSolutionPermuted(pb),currentSolutionPermuted(pb),node(node_),nbrNodes(p_) {
  lowerBoundL1 = 0 ;
  lowerBoundL2 = 0 ;
}


/**
 *
*/
void GSolverBBPv3::initBestSolutionWithFFD() {
    int nbrbatch=0 ;
    vector<double> tabRemainingCapacity ;

    for (int job=problem.getNP()-1;job>=0;job--) {
        // Find a suitable batch
        int batchjob = nbrbatch-1 ;
        bool found = false ;
        double jobsize = problem.getJobSize(job) ;
        while (!found && batchjob>=0) {
            if (tabRemainingCapacity[batchjob]>=jobsize) {
                found = true ;
            }
            else
                batchjob-- ;
        }

        if (!found) { // Create a new batch
            tabRemainingCapacity.insert(tabRemainingCapacity.begin(),problem.getTransporter(0).getCapacity()) ;
            for (int job2=job+1;job2<problem.getNP();++job2)
                bestSolutionPermuted.setBatchIndice(job2, bestSolutionPermuted.getBatchIndice(job2)+1) ;
            batchjob = 0 ;
            nbrbatch++ ;
	    bestSolutionPermuted.setNbrBatch(nbrbatch) ;
        }
        bestSolutionPermuted.setBatchIndice(job, batchjob+1) ;
        bestSolutionPermuted.setDeliveryCompletionTime(job, (double)batchjob+1) ;
        tabRemainingCapacity[batchjob] -= jobsize ;
    }

    bestSolutionPermuted.evaluate() ;
    //    if (!node) cout << "FFD evaluation = " << bestSolutionPermuted.getEvaluation() << endl ;
    if (!node) cout << " FFD=" << bestSolutionPermuted << endl ;
}



/**
 *
 */
void GSolverBBPv3::computeLowerBoundL1() {
  double totsize = 0.0 ;

  for (int job=0;job<problem.getNP();++job) {
    totsize +=  problem.getJobSize(job) ;
  }
  
  lowerBoundL1 = ceil ( totsize/problem.getTransporter(0).getCapacity() )  ;

  if (!node) {
    cout << "  lowerBoundL1 = " << lowerBoundL1 << endl ;
  }
}



int compareDecreasing (const void * a, const void * b)
{
  return ( *(double*)b - *(double*)a );
}

int compareIncreasing (const void * a, const void * b)
{
  return ( *(double*)a - *(double*)b );
}

/**
 *
 */
void GSolverBBPv3::computeLowerBoundL2() {
  int n = problem.getNP() ;
  double c = problem.getTransporter(0).getCapacity() ;

  computeLowerBoundL1() ;

  double weight[n+2] ;
  weight[0] = 0 ;
  for (int job=0;job<n;++job) {
    weight[job+1] = problem.getJobSize(job) ;
  }
  
  // if (!node) {
  //   cout << "weight before sort : " ;
  //   for (int job=0;job<=n;++job) {
  //     cout << weight[job] << "; " ;
  //   }
  //   cout << endl ;
  // }

  qsort(weight+1, n, sizeof(double), compareDecreasing) ;

  // if (!node) {
  //   cout << "weight after sort : " ;
  //   for (int job=0;job<=n;++job) {
  //     cout << weight[job] << "; " ;
  //   }
  //   cout << endl ;
  // }
  
  double capa_2 = c / 2.0 ;
  int jstar = n+1 ;

  for (int job=1;job<=n;++job) {
    if (weight[job]<=capa_2 && job < jstar) jstar = job ;
  }

  if (jstar==1) {
    lowerBoundL2 = lowerBoundL1 ;
    if (!node) {
      cout << "  lowerBoundL2 = L1 = " << lowerBoundL2 << endl ;
    }
    return ;
  }

  int CJ12 = jstar - 1 ; 

  double SJstar = 0.0 ;
  for (int j=jstar;j<=n;++j) SJstar += weight[j] ;

  int jprime = jstar ;
  for (int j=jstar-1;j>=1;--j) {
    if (j<jstar && weight[j]<=c-weight[jstar]) 
      jprime = j ;
  }

  int CJ2 = jstar-jprime ;

  double SJ2 = 0.0 ;
  for (int j=jprime;j<=jstar-1;++j) {
    SJ2 += weight[j] ;
  }

  int jsecond = jstar ;

  double SJ3 = weight[jsecond] ;
  
  weight[n+1] = 0.0 ;

  while (weight[jsecond+1]==weight[jsecond]) {
    jsecond = jsecond + 1 ;
    SJ3 = SJ3 + weight[jsecond] ;
  }
  
  lowerBoundL2 = CJ12 ;

  bool conditionFin = false ;
  while (!conditionFin) {

    double lowerBoundL2a = CJ12 + ceil( (SJ3+SJ2)/c - CJ2 ) ;
    if (lowerBoundL2a>lowerBoundL2) lowerBoundL2 = lowerBoundL2a ;

    jsecond++ ;
    if (jsecond<=n) {
      SJ3 += weight [jsecond] ;
      while (weight[jsecond+1]==weight[jsecond]) {
	jsecond++ ;
	SJ3 = SJ3+weight[jsecond] ;
      }
      
      while (jprime>1 && weight[jprime-1]<=c-weight[jsecond]) {
	jprime-- ;
	CJ2 = CJ2 +  1 ;
	SJ2 = SJ2 + weight[jprime] ;
      }
    }
    
    double lbstar = CJ12 + ceil( (SJstar+SJ2)/c - CJ2 ) ;
    conditionFin = (jsecond>n) || (lbstar <= lowerBoundL2 ) ;
  } 


  if (!node) {
    cout << "  lowerBoundL2 = " << lowerBoundL2 << endl ;
  }
  
}




/**
 *
 */
void GSolverBBPv3::solve() {
    solveInit() ;
    solveMain() ;
    solveEnd() ;
}


/**
 *
 */
void GSolverBBPv3::solveEnd() {
  if (!node) {
    // Transform "bestSolutionPermuted" to "bestSolution"
    bestSolution = this->problem.getBestSolutionFromBestSolutionPermuted(bestSolutionPermuted) ;
    cout << "=================================================================" << endl ;
    cout << "End of MASTER BBP : nbr batches=" << bestSolution.getNbrBatch() << " ; custHoldCost=" << bestSolution.getEvaluationCustomer() << " ; totEval=" << bestSolution.getEvaluation() << endl ;
    cout << "=================================================================" << endl ;
  }

  cpuComputingUsage = (double)100.0*cpuComputing.getTotalTime() / cpuTotal.getTotalTime() ;
  cpuMPICommUsage = (double)100.0*cpuMPIComm.getTotalTime() / cpuTotal.getTotalTime() ;

  cout << "Node " << node << " CPU computing usage =" << cpuComputingUsage << "%" << endl ;
  cout << "Node " << node << " >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> CPU MPI Comm  usage =" << cpuMPICommUsage << "%" << endl ;
}


